문제 소개

문제 링크 : https://boj.kr/3654

Tier : Diamond IV

Tag : 2-SAT

3칸을 차지하는 L모양의 퍼즐 조각이 있다. 중간은 검은 색이며, 나머지 두 칸은 하얀 색이다.

각 테스트 케이스마다 N * M 크기의 패턴이 주어지는데,

우리는 해당 퍼즐 조각을 적절히 놓았을 때 패턴을 온전히 만들 수 있는지에 대한 여부를 확인해야 한다.

이때, 퍼즐 조각은 회전 가능하지만 겹칠 수 없다.

풀이

1. 일반적인 규칙 찾기

패턴 내의

검은 색 칸을 기준으로 가로에 하얀 색 칸 하나, 세로에 하얀 색 칸 하나가 붙어 있어야 L모양이 성립한다. (a)
하얀 색 칸을 기준으로 인접하는 검은 색 칸 중 하나에만 포함되어야 한다. (b)

2. 유효하지 않은 케이스 찾기

패턴 내의

하얀 색 칸 개수가 검은 색 칸 개수의 정확히 두 배여야 한다. (c)
하얀 색 칸과 인접한 칸 중 검은 색 칸이 없으면 유효하지 않은 패턴이다. (d)
검은 색 칸 기준으로 각각 가로, 세로에 인접한 칸 중 하나라도 하얀 색 칸이 없으면 유효하지 않은 패턴이다. (e)

3. 위의 규칙을 토대로 2-SAT으로 모델링하기

어떻게 하면 이 규칙을 논리식으로 변환할 수 있을까?

특정 변수 a, b, c, ...에 대해,

(a v b) : a 또는 b가 true여야 성립

(a v a) : a가 true여야 성립

(!a v !b) ^ (!a v !c) ^ ... : a, b, c, ... 중 1개 이하만 true여야 성립

(!a v b) ^ (a v !b) ^ (!a v c) ^ (a v !c) ^ ... : a, b, c, ... 모두 true이거나 false여야 성립

등의 방식으로 논리식을 모델링할 수 있다.

맹점 1

이를 이용하여 **규칙 (b)**의 일부를 충족하지만, 검은 색 칸 전부 포함되지 않는 경우도 생길 수 있다.

그러나, 이 맹점은 규칙 (c)를 통해 해결할 수 있다.

왜냐하면, 저런 상황이 올 경우 하얀 색 칸이 남게 되기 때문이다.

맹점 2

특정한 검은 색 칸에 대해, 주변의 하얀 색 칸이 가로 세로당 하나씩만 붙어야 하는 **조건 (a)**는 어떻게 충족시켜야 할까?

이러한 문제점을 다음과 같은 변수 설정으로 해결할 수 있다.

검은 색 칸에 인접한 가로 칸 중, 왼쪽에 존재하는 하얀 칸을 false, 오른쪽에 존재하는 하얀 칸을 true로 간주하여 변수를 설정한다.

세로 칸의 경우에도 마찬가지이다.

특정 변수는 무조건 true 또는 false이므로, 논리식을 이용하지 않고 변수 설정만으로 해결할 수 있다.

나머지 규칙 (d), (e)의 경우 특정 칸에 겹치는 변수를 모두 몰아넣어 (b)를 구성할 때 같이 체크하면 된다.

코드

solution.cpp

1#include <bits/stdc++.h>
2#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
3
4#define BLANK 0
5#define BLACK 1
6#define WHITE 2
7#define MAX 1010101
8
9using namespace std;
10
11vector<int> nodes[502][502], graph[MAX];
12stack<int> candidate;
13
14int discovered[MAX], sccIDs[MAX];
15int puzzle[502][502];
16
17int nodeID, sccID;
18int N, M, whiteID;
19bool possible = true;
20
21// 테스트 케이스마다 초기화한다.
22void init() {
23    for (int i = 0; i < 502; i++) {
24        for (int j = 0; j < 502; j++) {
25            puzzle[i][j] = BLANK;
26            nodes[i][j] = vector<int>();
27        }
28    }
29
30    for (int i = 0; i < MAX; i++) {
31        graph[i] = vector<int>();
32    }
33
34    candidate = stack<int>();
35    possible = true;
36
37    nodeID = sccID = 1;
38    whiteID = 0;
39
40    memset(discovered, 0, sizeof discovered);
41    memset(sccIDs, 0, sizeof sccIDs);
42}
43
44// SCC를 형성한다.
45int createSCC(int node) {
46    int id = discovered[node] = nodeID++;
47    candidate.push(node);
48
49    for (auto next : graph[node]) {
50        if (!discovered[next])
51            id = min(id, createSCC(next));
52
53        else if (!sccIDs[next])
54            id = min(id, discovered[next]);
55    }
56
57    if (id == discovered[node]) {
58        while (true) {
59            int top = candidate.top();
60            candidate.pop();
61
62            sccIDs[top] = sccID;
63
64            if (top == node)
65                break;
66        }
67
68        sccID++;
69    }
70
71    return id;
72}
73
74// 패턴 매치가 가능한 지 체크한다.
75void check() {
76    for (int i = 0; i < whiteID; i++) {
77        if (!discovered[i]) createSCC(i);
78    }
79
80    for (int i = 0; i < whiteID; i += 4) {
81        int left = i, right = i + 1, top = i + 2, bottom = i + 3;
82
83        if ((sccIDs[left] == sccIDs[right]) || (sccIDs[top] == sccIDs[bottom])) {
84            possible = false;
85            return;
86        }
87    }
88}
89
90// 패턴 정보를 토대로 2-SAT 그래프를 모델링한다.
91void analyse() {
92    // 1. B 기준
93    for (int i = 1; i <= N; i++) {
94        for (int j = 1; j <= M; j++) {
95            if (puzzle[i][j] != BLACK) continue;
96
97            // 1-1. Horizontal
98            int left = whiteID, right = whiteID + 1;
99
100            if (puzzle[i][j - 1] == WHITE && puzzle[i][j + 1] == WHITE) {
101                nodes[i][j - 1].push_back(left);
102                nodes[i][j + 1].push_back(right);
103            }
104
105            else if (puzzle[i][j - 1] != WHITE && puzzle[i][j + 1] == WHITE) {
106                nodes[i][j + 1].push_back(right);
107
108                // 오른쪽 W가 무조건 들어가야 한다.
109                graph[left].push_back(right);
110            }
111
112            else if (puzzle[i][j - 1] == WHITE && puzzle[i][j + 1] != WHITE) {
113                nodes[i][j - 1].push_back(left);
114
115                // 왼쪽 W가 무조건 들어가야 한다.
116                graph[right].push_back(left);
117            }
118
119            // 둘 다 불가능한 경우 L퍼즐을 만들 수 없다.
120            else {
121                possible = false;
122                return;
123            }
124
125            // 1-2. Vertical
126            int top = whiteID + 2, bottom = whiteID + 3;
127
128            if (puzzle[i - 1][j] == WHITE && puzzle[i + 1][j] == WHITE) {
129                nodes[i - 1][j].push_back(top);
130                nodes[i + 1][j].push_back(bottom);
131            }
132
133            else if (puzzle[i - 1][j] != WHITE && puzzle[i + 1][j] == WHITE) {
134                nodes[i + 1][j].push_back(bottom);
135
136                // 아래쪽 W가 무조건 들어가야 한다.
137                graph[top].push_back(bottom);
138            }
139
140            else if (puzzle[i - 1][j] == WHITE && puzzle[i + 1][j] != WHITE) {
141                nodes[i - 1][j].push_back(top);
142
143                // 위쪽 W가 무조건 들어가야 한다.
144                graph[bottom].push_back(top);
145            }
146
147            // 둘 다 불가능한 경우 L퍼즐을 만들 수 없다.
148            else {
149                possible = false;
150                return;
151            }
152
153            whiteID += 4;
154        }
155    }
156
157    // 2. W 기준
158    for (int i = 1; i <= N; i++) {
159        for (int j = 1; j <= M; j++) {
160            if (puzzle[i][j] != WHITE) continue;
161
162            // W가 어떤 B에도 인접하지 않은 경우 L퍼즐을 만들 수 없다.
163            if (nodes[i][j].empty()) {
164                possible = false;
165                return;
166            }
167
168            int U = (int) nodes[i][j].size();
169
170            // 2-1. B가 하나인 경우, 이 W는 해당 B를 무조건 선택해야 한다.
171            if (U == 1) {
172                int v = nodes[i][j][0];
173                graph[v ^ 1].push_back(v);
174
175                continue;
176            }
177
178            // 2-2. 이들 중 두 개 이상을 만족시키지 않도록 한다.
179            for (int x = 0; x < U - 1; x++) {
180                int vx = nodes[i][j][x];
181
182                for (int y = x + 1; y < U; y++) {
183                    int vy = nodes[i][j][y];
184
185                    // (!x1 v !y1) = y1 -> x2, x1 -> y2
186                    graph[vy].push_back(vx ^ 1);
187                    graph[vx].push_back(vy ^ 1);
188                }
189            }
190        }
191    }
192}
193
194int main() {
195    FAST_IO;
196    int T; cin >> T;
197
198    while (T--) {
199        init();
200
201        // 1. 입력 받기
202        cin >> N >> M;
203
204        int white = 0, black = 0;
205
206        for (int i = 1; i <= N; i++) {
207            for (int j = 1; j <= M; j++) {
208                char c; cin >> c;
209
210                if (c == 'B') { black++; puzzle[i][j] = BLACK; }
211                if (c == 'W') { white++; puzzle[i][j] = WHITE; }
212                if (c == '.') { puzzle[i][j] = BLANK; }
213            }
214        }
215
216        if (white != black << 1) {
217            cout << "NO" << "\n";
218            continue;
219        }
220
221        // 2. 패턴을 그래프화
222        analyse();
223
224        if (!possible) {
225            cout << "NO" << "\n";
226            continue;
227        }
228
229        // 3. 패턴 매칭 체크
230        check();
231
232        cout << (possible ? "YES" : "NO") << "\n";
233    }
234
235    return 0;
236}
237

solution.cpp

1#include <bits/stdc++.h>
2#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
3
4#define BLANK 0
5#define BLACK 1
6#define WHITE 2
7#define MAX 1010101
8
9using namespace std;
10
11vector<int> nodes[502][502], graph[MAX];
12stack<int> candidate;
13
14int discovered[MAX], sccIDs[MAX];
15int puzzle[502][502];
16
17int nodeID, sccID;
18int N, M, whiteID;
19bool possible = true;
20
21// 테스트 케이스마다 초기화한다.
22void init() {
23    for (int i = 0; i < 502; i++) {
24        for (int j = 0; j < 502; j++) {
25            puzzle[i][j] = BLANK;
26            nodes[i][j] = vector<int>();
27        }
28    }
29
30    for (int i = 0; i < MAX; i++) {
31        graph[i] = vector<int>();
32    }
33
34    candidate = stack<int>();
35    possible = true;
36
37    nodeID = sccID = 1;
38    whiteID = 0;
39
40    memset(discovered, 0, sizeof discovered);
41    memset(sccIDs, 0, sizeof sccIDs);
42}
43
44// SCC를 형성한다.
45int createSCC(int node) {
46    int id = discovered[node] = nodeID++;
47    candidate.push(node);
48
49    for (auto next : graph[node]) {
50        if (!discovered[next])
51            id = min(id, createSCC(next));
52
53        else if (!sccIDs[next])
54            id = min(id, discovered[next]);
55    }
56
57    if (id == discovered[node]) {
58        while (true) {
59            int top = candidate.top();
60            candidate.pop();
61
62            sccIDs[top] = sccID;
63
64            if (top == node)
65                break;
66        }
67
68        sccID++;
69    }
70
71    return id;
72}
73
74// 패턴 매치가 가능한 지 체크한다.
75void check() {
76    for (int i = 0; i < whiteID; i++) {
77        if (!discovered[i]) createSCC(i);
78    }
79
80    for (int i = 0; i < whiteID; i += 4) {
81        int left = i, right = i + 1, top = i + 2, bottom = i + 3;
82
83        if ((sccIDs[left] == sccIDs[right]) || (sccIDs[top] == sccIDs[bottom])) {
84            possible = false;
85            return;
86        }
87    }
88}
89
90// 패턴 정보를 토대로 2-SAT 그래프를 모델링한다.
91void analyse() {
92    // 1. B 기준
93    for (int i = 1; i <= N; i++) {
94        for (int j = 1; j <= M; j++) {
95            if (puzzle[i][j] != BLACK) continue;
96
97            // 1-1. Horizontal
98            int left = whiteID, right = whiteID + 1;
99
100            if (puzzle[i][j - 1] == WHITE && puzzle[i][j + 1] == WHITE) {
101                nodes[i][j - 1].push_back(left);
102                nodes[i][j + 1].push_back(right);
103            }
104
105            else if (puzzle[i][j - 1] != WHITE && puzzle[i][j + 1] == WHITE) {
106                nodes[i][j + 1].push_back(right);
107
108                // 오른쪽 W가 무조건 들어가야 한다.
109                graph[left].push_back(right);
110            }
111
112            else if (puzzle[i][j - 1] == WHITE && puzzle[i][j + 1] != WHITE) {
113                nodes[i][j - 1].push_back(left);
114
115                // 왼쪽 W가 무조건 들어가야 한다.
116                graph[right].push_back(left);
117            }
118
119            // 둘 다 불가능한 경우 L퍼즐을 만들 수 없다.
120            else {
121                possible = false;
122                return;
123            }
124
125            // 1-2. Vertical
126            int top = whiteID + 2, bottom = whiteID + 3;
127
128            if (puzzle[i - 1][j] == WHITE && puzzle[i + 1][j] == WHITE) {
129                nodes[i - 1][j].push_back(top);
130                nodes[i + 1][j].push_back(bottom);
131            }
132
133            else if (puzzle[i - 1][j] != WHITE && puzzle[i + 1][j] == WHITE) {
134                nodes[i + 1][j].push_back(bottom);
135
136                // 아래쪽 W가 무조건 들어가야 한다.
137                graph[top].push_back(bottom);
138            }
139
140            else if (puzzle[i - 1][j] == WHITE && puzzle[i + 1][j] != WHITE) {
141                nodes[i - 1][j].push_back(top);
142
143                // 위쪽 W가 무조건 들어가야 한다.
144                graph[bottom].push_back(top);
145            }
146
147            // 둘 다 불가능한 경우 L퍼즐을 만들 수 없다.
148            else {
149                possible = false;
150                return;
151            }
152
153            whiteID += 4;
154        }
155    }
156
157    // 2. W 기준
158    for (int i = 1; i <= N; i++) {
159        for (int j = 1; j <= M; j++) {
160            if (puzzle[i][j] != WHITE) continue;
161
162            // W가 어떤 B에도 인접하지 않은 경우 L퍼즐을 만들 수 없다.
163            if (nodes[i][j].empty()) {
164                possible = false;
165                return;
166            }
167
168            int U = (int) nodes[i][j].size();
169
170            // 2-1. B가 하나인 경우, 이 W는 해당 B를 무조건 선택해야 한다.
171            if (U == 1) {
172                int v = nodes[i][j][0];
173                graph[v ^ 1].push_back(v);
174
175                continue;
176            }
177
178            // 2-2. 이들 중 두 개 이상을 만족시키지 않도록 한다.
179            for (int x = 0; x < U - 1; x++) {
180                int vx = nodes[i][j][x];
181
182                for (int y = x + 1; y < U; y++) {
183                    int vy = nodes[i][j][y];
184
185                    // (!x1 v !y1) = y1 -> x2, x1 -> y2
186                    graph[vy].push_back(vx ^ 1);
187                    graph[vx].push_back(vy ^ 1);
188                }
189            }
190        }
191    }
192}
193
194int main() {
195    FAST_IO;
196    int T; cin >> T;
197
198    while (T--) {
199        init();
200
201        // 1. 입력 받기
202        cin >> N >> M;
203
204        int white = 0, black = 0;
205
206        for (int i = 1; i <= N; i++) {
207            for (int j = 1; j <= M; j++) {
208                char c; cin >> c;
209
210                if (c == 'B') { black++; puzzle[i][j] = BLACK; }
211                if (c == 'W') { white++; puzzle[i][j] = WHITE; }
212                if (c == '.') { puzzle[i][j] = BLANK; }
213            }
214        }
215
216        if (white != black << 1) {
217            cout << "NO" << "\n";
218            continue;
219        }
220
221        // 2. 패턴을 그래프화
222        analyse();
223
224        if (!possible) {
225            cout << "NO" << "\n";
226            continue;
227        }
228
229        // 3. 패턴 매칭 체크
230        check();
231
232        cout << (possible ? "YES" : "NO") << "\n";
233    }
234
235    return 0;
236}
237